public class Solution1249 {
    public String minRemoveToMakeValid(String s) {
        StringBuilder stringBuilder=new StringBuilder();
        int count=0;
        for (char c : s.toCharArray()) {
            if (c=='('){
                stringBuilder.append('(');
                count++;
            }else if (c==')'){
                if (count>0){
                    stringBuilder.append(')');
                    count--;
                }
            }else {
                stringBuilder.append(c);
            }
        }
        StringBuilder ans=new StringBuilder();
        for (int i=stringBuilder.length()-1;i>=0;i--){
            if (stringBuilder.charAt(i)=='(' && count>0){
                count--;
            }else {
                ans.append(stringBuilder.charAt(i));
            }
        }
        return ans.reverse().toString();
    }

    public static void main(String[] args) {
        System.out.println(new Solution1249().minRemoveToMakeValid("a)b(c)d"));
    }
}
